package ljl.alg.wangzheng_camp.round1.backtrack;

import java.util.ArrayList;
import java.util.List;
import java.util.stream.IntStream;

public class _77_comb {
    
    List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> combine(int n, int k) {
        backtrack(new ArrayList<>(), 1, k, n);
        return res;
    }
    void backtrack(List<Integer> cur, int i, int k, int n) {
        if (cur.size() + n - i + 1 < k) return;
        if (cur.size() == k) {
            res.add(new ArrayList<>(cur));
        } else {
            backtrack(cur, i + 1, k, n);
            cur.add(i);
            backtrack(cur, i + 1, k, n);
            cur.remove(cur.size() - 1);
        }
    }
    
    /*
    * 过一阵必然就忘了，太玄学了
    * */
    static class metaphysics {
    
        public List<List<Integer>> combine(int n, int k) {
            List<List<Integer>> res = new ArrayList<>();
            List<Integer> tmp = new ArrayList<>();
            IntStream.range(1, k + 1).forEach(tmp::add);
            tmp.add(n + 1);
            int j = 0;
            while (j < k) {
                res.add(new ArrayList<>(tmp.subList(0, k)));
                j = 0;
                while (j < k && tmp.get(j) + 1 == tmp.get(j + 1)) tmp.set(j, (j++ + 1));
                tmp.set(j, tmp.get(j) + 1);
            }
            return res;
        }
    }
    
}
